package lru;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU: 最近最少使用 缓存机制
 * 解题思路：
 * 1、利用 HashMap + 双向链表解题
 * HashMap 存储 key + Node
 * 查询的时间复杂度为 O(1)
 * 2、双向链表,最新的缓存
 * <p>
 * 实现：
 * 1、需要先定义一个 双向链表的数据结构
 * 2、为了操作方便，双向链表添加 伪头节点 和 伪尾节点
 */
public class LRUCache {

    class DoubleLinkedNode {
        int key;
        int value;
        DoubleLinkedNode prev;
        DoubleLinkedNode next;

        public DoubleLinkedNode() {

        }

        public DoubleLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    int size; // 当前大小
    int capacity; // 缓存可用大小
    private Map<Integer, DoubleLinkedNode> map = new HashMap<Integer, DoubleLinkedNode>(); // 缓存 map
    DoubleLinkedNode head; // 伪头节点
    DoubleLinkedNode tail; // 伪尾节点

    /**
     * 初始化
     * @param capacity
     */
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.head = new DoubleLinkedNode();
        this.tail = new DoubleLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 时间复杂度为 ： O(1)
     *  分析：
     *      根据 key 在 map 中查找 ；时间复杂度为 ： O(1)
     *      1、map 中存在
     *          1.1 找到 key 对应的 DoubleLinkedNode ,
     *          1.2 在 双向链表中 将当前节点 移动到 最前面 （head.next）
     *              1.2.1   在双向链表中删除当前节点
     *              1.2.2   将当前节点添加到最前面 （head.next）
     *      2、map 中不存在
     *          return -1;
     * @param key
     * @return
     */
    public int get(int key) {
        DoubleLinkedNode node = map.get(key); // key = 3,value = 3
        if(node == null){
            return -1;
        }
        moveToHead(node);
        return node.value;

    }

    /**
     * 时间复杂度为： O(1)
     *  怎么移动到最前面
     *  1、先删除当前节点
     *  2、添加到最前面
     * @param node
     */
    private void moveToHead(DoubleLinkedNode node) {
        removeNode(node);
        addHead(node);
    }

    /**
     * 时间复杂度为 ：O(1)
     * 将当前节点添加到 最前面 （head.next）
     *          9
     *   (head) <=> 1 <=> 2 <=> 3 <=> 4 <=> (tail)
     *   node.next = head.next; 9 -> 1
     *   node.prev = head;      9 -> head
     *   head.next.prev = node; 1 -> 9
     *   head.next = node       head -> 9
     * @param node
     */
    private void addHead(DoubleLinkedNode node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    /**
     * 时间复杂度为：O(1)
     * 怎么删除？
     *  单链表怎么删除？
     *      时间复杂度为： O(1)
     *      为什么是 O(1)? 删除这个操作是 O(1),不包含查找操作，
     *      假如说 删除 3，得先找到 2 节点吧，
     *      2.next = 2.next.next
     *       1 -> 2 -> 3->4
     *       1 -> 2 -> 4
     *  双向链表怎么删除？
     *      时间复杂度为 ：O(1)，不需要查找，
     *       1 <=> 2 <=> 3 <=> 4
     *       1 <=> 2 <=> 4
     *       删除 3 这个节点，怎么做？
     *       3.prev.next = 3.next
     *       3.next.prev = 3.prev
     * @param node
     */
    private void removeNode(DoubleLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /**
     *  分析：
     *      根据 key 在 map 中查找吧，时间复杂度为：O(1)
     *      1、map 中存在
     *          1.1 找到 key 对应的 DoubleLinkedNode
     *          1.2 修改节点对应的 value
     *          1.3 将当前节点移动过到最前面 （head.next）
     *              1.3.1   在双向链表删除当前节点
     *              1.3.2   将当前节点 添加到最前面 （head.next）
     *      2、map 中不存在
     *          2.1  新建一个 DoubleLinkedNode node (map.put(key,node))
     *          2.2  是不是需要考虑 （缓存） 双向链表的容量大小？
     *              2.2.1 未达到容量，
     *                  将当前节点添加到最前面 （head.next）
     *              2.2.2  达到了容量大小
     *                  将当前节点添加到最前面，(head.next)
     *                  然后呢？ 移除最后面一个节点 （tail.prev）
     *                      node = tail.prev ;是不是相当于移除当前节点
     *                      并且将最后一个节点 对应的 key 在 map 中移除？
     *                      map.remove(node.key);
 *
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        DoubleLinkedNode node = map.get(key);
        if(node != null){
            node.value = value;
            moveToHead(node);
        }else{
            DoubleLinkedNode newNode = new DoubleLinkedNode(key, value);
            map.put(key,newNode);
            addHead(newNode);
            size++;
            if(size > capacity){ // 当前大小 大于 容量大小
                DoubleLinkedNode last = tail.prev;
                removeNode(last);
                map.remove(last.key);
                size--;
            }
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */